543. 二叉树的直径

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

关键是要注意到一点: 对于单棵子树而言, 最长的直径等于左子树的深度 + 右子树的深度

但是当深度向上传递的时候, 只有左右子树中更深的那个适合与更大的树结合在一起形成更大的直径

var diameterOfBinaryTree = function(root) {
    let result = 0

    function getDepth(root) {
        if(!root) return 0

        const leftDepth = getDepth(root.left)
        const rightDepth = getDepth(root.right)

        result = Math.max(result,(leftDepth + rightDepth ))

        return Math.max(leftDepth,rightDepth) + 1
    }

    getDepth(root)

    return result
};